package com.julius.design.suanfa.tree;


import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author julius
 * @date 2021-11-12 上午 11:45
 * <p>
 *      二叉树的最大深度
 *
 * </p>
 */
public class MaxDepthTree {


    /**
     * 二叉树的最大深度
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root){
        int bfs = bfs(root);
        int dfs = dfs(root);
        return dfs;

    }


    /**
     * 深度优先搜索
     *      往往利用栈或者递归实现
     *      树的深度等于左子树的深度和右子树的深度最大值+1
     * @param root
     * @return
     */
    public int dfs(TreeNode root){
        if(root == null){
            return 0;
        }
        return Math.max(dfs(root.left),dfs(root.right))+1;
    }

    /**
     * 深度优先搜索  DFS
     *
     * 利用栈实现迭代搜索
     * @param root
     * @return
     */
    public int dfsStack(TreeNode root){
        //栈，先进后出  前序遍历 父 左  右
        Deque<TreeNode> stack = new LinkedList<>();

        int level = 0;

        TreeNode pre = null;


        while (root != null || !stack.isEmpty()){
            while (root != null){
                stack.push(root);
                root = root.left;
                level++;
            }

            //弹出节点
            root = stack.pop();

            //该节点含有右节点，则先加入右节点
            if(root.right == null || pre == root.right){
                pre = root;
                //使得当前节点前移一位
                root = null;
                level--;

            }else{
                stack.push(root);
                root = root.right;
                level++;
            }
        }
        return level+1;
    }

    /**
     * BFS 广度优先搜索
     * @param root
     * @return
     */
    public int bfs(TreeNode root){
        if(root == null){
            return 0;
        }

        int level = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();

                if (cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
            }
            level++;
        }
        return level;
    }





    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
}
